//爬楼梯   5
//1 1 1 1 1
//2 1 1 1
//1 2 1 1
//1 1 2 1
//1 1 1 2
//2 2 1
//2 1 2
//1 2 2

//达到某个目的的所有的解的个数
//只要解的个数，不需要具体的解

//动态规划

// function climbStairs(n) {
//   if (n <= 3) {
//     return n;
//   }
//   return climbStairs(n - 1) + climbStairs(n - 2);
// }
// console.log(climbStairs(5));
//  这是递归来解这个问题  时间过不去

// const f = [0, 1, 2, 3];
// var climbStairs = function (n) {
//   if (n <= 2) {
//     return f[n];
//   }
//   if (f[n] == undefined) {
//     f[n] = climbStairs(n - 1) + climbStairs(n - 2);
//   }
//   return f[n];
// };
// console.log(climbStairs(5));
//  记忆化优化  但还不是动态规划

// f(n) = f(n - 1) + f(n - 2)  //动态推导方程

var climbStairs = function (n) {
  const f = [];
  f[1] = 1;
  f[2] = 2;
  for (let i = 3; i <= n; i--) {
    f[i] = f[i - 1] + f[i - 2];
  }
  return f[n];
};
